package org.example.myleet.p763;

import java.util.ArrayList;
import java.util.List;

/**
 * 执行用时：4 ms, 在所有 Java 提交中击败了86.91%的用户
 * 内存消耗：37 MB, 在所有 Java 提交中击败了97.06%的用户
 *
 * 此答案参考别人
 */
public class Solution2 {

    public List<Integer> partitionLabels(String S) {
        if (0 == S.length()) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
        int[] characterMaxEndMap = new int[26];
        //第一次遍历，记录每一个字母的最远位置
        for (int i=0; i<S.length(); i++) {
            characterMaxEndMap[S.charAt(i) - 'a'] = i;
        }
        int start = 0, end = 0;
        //第二次遍历是解题关键
        for (int i=0; i<S.length(); i++) {
            //对于遇到的每一个字母，其最远的那个出现位置决定了其所在的字符串的最远位置
            //max结果的结果，要么是上一个字符串最远位置end，要么是游标字符的最远位置，更新到end中
            //因此max结果end是整个字符串中字母的最远位置
            end = Math.max(end, characterMaxEndMap[S.charAt(i) - 'a']);
            if (i == end) {
                //当游标遇上某个整个字符串的最远位置，也就意味着这是字符串的结束，记录结果
                result.add(end - start + 1);
                //start就是end的下一个字符，是下一个字符串的开始位置，用于计算下一个字符串的长度
                start = i + 1;
            }
        }
        return result;
    }
}
